package com.gxc.rapacity;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给你如下数据：
 * 数组arr：数组长度表示一共有几台咖啡机，数组中的数值代表每台咖啡机各自制作一杯咖啡需要的时间，
 * 例如arr=[3,2,7]就表示一共有三台咖啡机，第一台咖啡机制作一杯咖啡需要3单位时间，第二台需要2单位时间，第三台需要7单位时间。
 * int N：表示有N个人需要用咖啡机制作咖啡，每人一杯，同时，假设制作完咖啡后，喝咖啡时间为0。
 * int a：表示用洗碗机洗一个咖啡杯需要的时间，只有一台，每次只洗一个咖啡杯。
 * int b：表示咖啡杯也可以不洗，自然晾干的时间。咖啡杯要么洗，要么晾干。
 * 现在，请你求出这N个人从开始用咖啡机制作咖啡到所有杯子洗好或者晾干的最少时间？
 *
 * 解法：
 *
 * 贪心
 * i顾客选择咖啡机的时间（建立一个咖啡机类，咖啡机编号和咖啡机最早空闲时刻）
 * 由小根堆（咖啡机的工作时间+每杯咖啡的时间排序）记录每个咖啡机完成的时间，每次弹出堆顶就是当前咖啡机空闲的时间，
 * 可以形成每个顾客喝到咖啡时间的一个数组
 *
 * 暴力递归尝试：
 * i顾客选择咖啡机洗杯子的时间
 * 第i杯被洗碗机洗碗的时间和后续所有杯子洗完的时间取大值
 *
 * i顾客选择杯子晾干的时间
 * 第i杯晾干的时间和后续所有杯子洗完的时间取大值
 *
 * 两个时间取小值
 */
public class CoffeeMachine {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 7};
    }

    /**
     * 错误，自写方法
     * i顾客选择咖啡机的时间
     * 建立一个小根堆，按按咖啡机使用时间排序，顾客使用时，弹出时间最小的咖啡机
     * @param arr
     * @param n
     * @param a
     * @param b
     * @return
     */
    public static int minTime(int[] arr, int n ,int a, int b) {
        if (arr.length < 0 || n < 0 || a < 0 || b < 0) {
            return -1;
        }
        //建立一个小根堆，按按咖啡机使用时间排序，顾客使用时，弹出时间最小的咖啡机
        PriorityQueue<LeisureMachine> queue = new PriorityQueue<>(new LeisureMachineComparator());
        for (int i = 0; i < arr.length; i++) {
            queue.add(new LeisureMachine(i, arr[i], 0));
        }

        return process(arr, 0, n, 0, a, 0, b, 0, queue);
    }

    /**
     * 错误，自写方法
     * @param arr
     * @param ni 当前第i个顾客
     * @param n
     * @param ai ai个顾客选择咖啡机洗杯子
     * @param a
     * @param bi bi个顾客选择杯子晾干
     * @param b
     * @param queue
     * @return
     */
    private static int process(int[] arr, int ni,int n, int ai,int a, int bi, int b, int total,
                               PriorityQueue<LeisureMachine> queue) {
        //cur 从0开始，所以到n结束
        if (ni == n) {
            return total;
        }
        //弹出时间最小的咖啡机，咖啡机的使用时间增加
        LeisureMachine poll = queue.poll();
        int time = poll.time + arr[poll.num];
        queue.add(new LeisureMachine(poll.num, arr[poll.num], time));
        //等待洗碗机洗咖啡杯的时间
        int time1 = (ai+1)*a;
        //等待杯子晾干
        int time2 = (bi+1)*b;
        int minWait = 0;
        if (time1>time2) {
            ai = ai+1;
        } else if (time1<time2) {
            bi = bi+1;
        }
        //时间时间=咖啡机时间+洗碗时间
        int actul = time + minWait;
        return process(arr, ni+1, n, ai, a, bi, b, actul, queue);
    }

    /**
     *
     * @param arr
     * @param n
     * @param a
     * @param b
     * @return
     */
    public static int minTime2(int[] arr, int n ,int a, int b) {
        if (arr.length < 0 || n < 0 || a < 0 || b < 0) {
            return -1;
        }
        //建立一个小根堆，按按咖啡机使用时间排序，顾客使用时，弹出时间最小的咖啡机
        PriorityQueue<LeisureMachine> queue = new PriorityQueue<>(new LeisureMachineComparator());
        for (int i = 0; i < arr.length; i++) {
            queue.add(new LeisureMachine(i, arr[i], 0));
        }
        //i杯咖啡做好的时间
        int[] time = new int[n];
        for (int i = 0; i < n; i++) {
            LeisureMachine poll = queue.poll();
            time[i] = poll.time + poll.usetime;
            queue.add(new LeisureMachine(poll.num, poll.usetime, time[i]));
        }

        return wash(time, 0, a, b, 0);
    }

    /**
     *
     * @param time  i杯咖啡做好的时间
     * @param i  i杯
     * @param a
     * @param b
     * @param washTime 洗碗机的时间
     * @return
     */
    private static int wash(int[] time, int i, int a, int b, int washTime) {
        //第i个顾客咖啡做好的时间
        int startTime = time[i];
        if (i == time.length-1) {
            //time[i]+b   i杯咖啡做好的时间+杯子晾干的时间
            //Math.max(washTime, startTime)+a  由于不知道是洗碗机还是咖啡机先空闲，只能取两个最大的工作时间+洗杯子的时间
            return Math.min(startTime + b, Math.max(washTime, startTime) + a);
        }
        //第i个顾客采用洗碗机的时间
        int aWashTime = Math.max(washTime, startTime) + a;
        //由于当前时间可能比后续所有时间都慢,所以比较两者的最大值就是 第i个杯子洗好的时间
        int aNextTime = wash(time, i+1, a, b, aWashTime);
        int p1 = Math.max(aWashTime, aNextTime);
        //第i个顾客采用晾干的时间
        int bTime = startTime+b;
        //由于当前时间可能比后续所有时间都慢,所以比较两者的最大值就是 第i个杯子洗好的时间
        int bNextTime = wash(time, i+1, a, b, washTime);
        int p2 = Math.max(bTime, bNextTime);
        return Math.min(p1, p2);
    }

    /**
     * 递归转dp
     * wash(time, 0, a, b, 0)
     * 根据递归，返回dp[0][0]的数据
     * @param time
     * @param a
     * @param b
     * @return
     */
    private static int dp(int[] time,int a, int b) {
        //如果洗碗机洗杯子的时间大于晾干的时间，直接选择晾干就行
        if (a>=b) return time[time.length-1] + b;
        //washTime 最坏情况就是所有杯子等喝完才一起洗
        int washTime = time[time.length-1] + time.length * a;
        int length = time.length;
        int[][] dp = new int[length][washTime];
        for (int j = 0; j < washTime; j++) {
            dp[length-1][j] = Math.min(time[length-1] + b, Math.max(j, time[length-1]) + a);
        }

        for (int i = length-2; i >= 0; i++) {
            for (int j = 0; j < washTime; j++) {
                //第i个顾客采用洗碗机的时间
                int aWashTime = Math.max(j, time[i]) + a;
                //由于当前时间可能比后续所有时间都慢,所以比较两者的最大值就是 第i个杯子洗好的时间
                int aNextTime = dp[i+1][aWashTime];
                int p1 = Math.max(aWashTime, aNextTime);
                //第i个顾客采用晾干的时间
                int bTime = time[i]+b;
                //由于当前时间可能比后续所有时间都慢,所以比较两者的最大值就是 第i个杯子洗好的时间
                int bNextTime = dp[i+1][j];
                int p2 = Math.max(bTime, bNextTime);

                dp[i][j] = Math.min(p1, p2);
            }
        }

        return dp[0][0];
    }

    /**
     * 递归转dp
     * 加速
     * wash(time, 0, a, b, 0)
     * 根据递归，返回dp[0][0]的数据
     * @param time
     * @param a
     * @param b
     * @return
     */
    private static int dp2(int[] time,int a, int b) {
        //如果洗碗机洗杯子的时间大于晾干的时间，直接选择晾干就行
        if (a>=b) return time[time.length-1] + b;
        //washTime 最坏情况就是所有杯子等喝完才一起洗
        int washTime = time[time.length-1] + time.length * a;
        int length = time.length;
        int[][] dp = new int[length][washTime];
        for (int j = 0; j < washTime; j++) {
            dp[length-1][j] = Math.min(time[length-1] + b, Math.max(j, time[length-1]) + a);
        }

        for (int i = length-2; i >= 0; i++) {
            //加速，当前没喝到的咖啡不需要洗
            int available = time[i] + (i + 1) * a;
            for (int j = 0; j < available; j++) {
                //第i个顾客采用洗碗机的时间
                int aWashTime = Math.max(j, time[i]) + a;
                //由于当前时间可能比后续所有时间都慢,所以比较两者的最大值就是 第i个杯子洗好的时间
                int aNextTime = dp[i+1][aWashTime];
                int p1 = Math.max(aWashTime, aNextTime);
                //第i个顾客采用晾干的时间
                int bTime = time[i]+b;
                //由于当前时间可能比后续所有时间都慢,所以比较两者的最大值就是 第i个杯子洗好的时间
                int bNextTime = dp[i+1][j];
                int p2 = Math.max(bTime, bNextTime);

                dp[i][j] = Math.min(p1, p2);
            }
        }

        return dp[0][0];
    }


    public static class LeisureMachine {

        /**
         * 咖啡机编号
         */
        public int num;
        /**
         * 咖啡机每次使用时间
         */
        public int usetime;
        /**
         * 咖啡机最早空闲时刻
         */
        public int time;

        public LeisureMachine(int num, int usetime, int time) {
            this.num = num;
            this.usetime = usetime;
            this.time = time;
        }
    }

    public static class LeisureMachineComparator implements Comparator<LeisureMachine> {

        @Override
        public int compare(LeisureMachine o1, LeisureMachine o2) {
            return o1.time + o1.usetime - o2.time - o2.usetime;
        }
    }

}
